package com.south.base.test.arithmetic.dynamic.programming;

import org.junit.Assert;
import org.junit.Test;

/**
 * @author Administrator
 * @date 2019/8/30 11:05
 */
public class JumpPath {
    /**
     * 跳跃游戏
     * 给出一个非负整数数组，你最初定位在数组的第一个位置。
     * 数组中的每个元素代表你在那个位置可以跳跃的最大长度。
     * 判断你是否能到达数组的最后一个位置。
     */
    @Test
    public void canJump() {
        Assert.assertTrue(canJump(new int[]{2, 3, 1, 1, 4}));
        Assert.assertFalse(canJump(new int[]{3, 2, 1, 0, 4}));
    }

    public boolean canJump(int[] A) {
        boolean[] f = new boolean[A.length];
        f[0] = true;
        for (int i = 1; i < A.length; i++) {
            for (int j = 0; j < i; j++) {
                if (f[j] && j + A[j] >= i) {
                    f[i] = true;
                    break;
                }
            }
        }
        return f[A.length - 1];
    }

    public boolean canJump2(int[] nums) {
        if (nums.length == 0) {
            return true;
        }
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0 && max <= i && i < nums.length - 1) {
                return false;
            }
            max = Math.max(max, nums[i] + i);
        }
        return true;
    }

    /**
     * 跳跃游戏 II
     * 给定一个非负整数数组，你最初位于数组的第一个位置。
     * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
     * 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
     */
    @Test
    public void jump() {
        Assert.assertEquals(2, jump(new int[]{2, 3, 1, 1, 4}));
    }

    public int jump(int[] nums) {
        int[] dp = new int[nums.length];
        dp[0] = 0;
        int max = nums[0];
        for (int i = 0; i < dp.length - 1; ) {
            int tmpMax = max;
            for (int j = i + 1; j <= tmpMax && j < dp.length; j++) {
                dp[j] = dp[i] + 1;
                max = Math.max(max, nums[j] + j);
            }
            i = tmpMax;
        }
        return dp[dp.length - 1];
    }
}
